[Coding026] Sort - 桶排序

Bucket-sort

More coding records

Get the knowledge flowing and circulating! :)

目录

标题：桶排序

桶排序（英语：Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（$\mathrm{\Theta }(n)$$\Theta(n)$）。

桶排序以下列程序进行：

1. 设置一个定量的数组当作空桶子。

2. 寻访序列，并且把项目一个一个放到对应的桶子去。

3. 对每个不是空的桶子进行排序。

4. 从不是空的桶子里把项目再放回原来的序列中。

——维基百科

【补充笔记】

Definition：Stable sorting algorithm

A sorting algorithm that preserves the order of items with identical key。

INPUT: (1,x), (6,m), (4,k), (5,t), (2,s), (3,b), (1,a), (6,f), (6,b) → 解释：(3, b)中，3是key，b是object

Example of stable output:

OUTPUT: (1,x), (1,a), (2,s), (3,b), (4,k), (5,t), (6,m), (6,f), (6,b)

---

问题：至今似乎我们看到的排序最好的时间复杂度为$O(n\log n)$$O(n\log n)$，有没有可能还有更好的排序算法呢？

回答：没了。一般来说，$\mathrm{\Omega }(n\log n)$$\Omega(n\log n)$的问题有一个下界，但是在某些情况下，$O(n)$$O(n)$也是可能的。

桶排序 vs Others

Imagine putting 200 student papers in alphabetical order according to the first letter of the last name. An insertion sort (or selection sort, or bubbleSort) would have us try to deal with the whole pile at once. Merge-sort would require spreading out all 200 papers and then comparing and piling them back up again in order.

想象一下，把200名学生的论文按照姓氏的首字母顺序排列。插入排序(或选择排序，或冒泡排序)会让我们尝试一次处理整个堆。归并排序需要将所有200份文件展开，然后再按顺序进行比较和堆积。

Bucket-Sort has us place them into 26 piles by first letter and then stacking those piles together.

桶式排序让我们按照首字母将它们分成26堆，然后将这些摞在一起。

桶排序思想和复杂度

• Let be $S$$S$ be a sequence of $n$$n$ (key, element) items with keys in the range $[0,N-1]$$[0, N − 1]$

  设S为一个由N(key, element)项组成的序列，这些项的键值范围为[0, N−1]

• Bucket-sort uses the keys as indices into an auxiliary array $B$$B$ of sequences (buckets)

  • Phase 1: Empty sequence $S$$S$ by moving each item $(k,o)$$(k, o)$ into its bucket $B[k]$$B[k]$

  • Phase 2: For $i=0,\dots ,N-1$$i = 0, …, N − 1$, move the items of bucket $B[i]$$B[i]$ to the end of sequence $S$$S$

  桶排序使用键作为索引进入一个辅助数组B的序列(桶)
  阶段1：通过将每个元素(k,o)移动到桶B[k]中来清空序列S。
  阶段2：当i = 0，…，N−1时，将桶B[i]中的项移动到序列S的末尾。

• Analysis:

  • Phase 1 takes $O(n)$$O(n)$ time

  • Phase 2 takes $O(n+N)$$O(n + N)$ time

Bucket-sort takes $O(n+N)$$O(n + N)$ time.

算法伪代码（Pseudo-code）

实际案例

特性（Properties）

Key-type Property（键的类型的性质）

• The keys are used as indices into an array and cannot be arbitrary objects

  键必须是数组的下标，不能是任意的对象。

• No external comparator

  没有额外的比较器。

Stable Sort Property（排序的稳定性）

• The relative order of any two items with the same key is preserved after the execution of the algorithm

  算法执行结束后，任意2个元素的相对顺序不会变化。

拓展（Extensions）

• Integer keys in the range $[a,b]$$[a, b]$

  如果键是整型数，并且范围在$[a,b]$$[a, b]$之间

  • Put item $(k,o)$$(k, o)$ into bucket $B[k-a]$$B[k − a]$

    把每条记录存放在桶$B[k-a]$$B[k − a]$对应的位置中

• String keys from a set $D$$D$ of possible strings, where $D$$D$ has constant size

  如果键是字符串，字符串来自于集合 $D$$D$（ $D$$D$ 的大小为常数）。

  • Sort $D$$D$ and compute the rank $r(k)$$r(k)$ of each string $k$$k$ of $D$$D$ in the sorted sequence

    把 $D$$D$ 按照字符首字母排序，并且在已排序的序列中计算 $D$$D$ 中的每个字符串 $k$$k$ 的顺序 $r(k)$$r(k)$

  • Put item $(k,o)$$(k, o)$ into bucket $B[r(k)]$$B[r(k)]$

    把记录 $(k,o)$$(k, o)$ 放进桶 $B[r(k)]$$B[r(k)]$中。

实例